//题目:
// 有 n 个城市通过一些航班连接。
// 给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

// 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，
// 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;
//代码
class Solution 
{
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) 
    {
        //1.创建dp表————dp[i][j]表示：最多转机i次，到达j城市，所花费的最少钱
        vector<vector<int>> dp(k+2,vector<int>(101,0xffffff));
        //2.初始化
        dp[0][src]=0;
        //3.填表————动态转移方程：
        int ret=INT_MAX;
        for(int i=1;i<=k+1;i++)
        {
            for(int j=0;j<=100;j++)
            {
                for(auto& v:flights)
                {
                    if(v[1]==j && dp[i-1][v[0]]!=INT_MAX)
                        dp[i][j]=min(dp[i][j],dp[i-1][v[0]]+v[2]);
                }
                if(j==dst) ret=min(ret,dp[i][j]);
            }
        }
        //4.确定返回值
        return ret==0xffffff?-1:ret;
    }
};